#include <vector>
#include <unordered_map>

using namespace std;


class Solution {
public:

    // 525. 连续数组
    // https://leetcode.cn/problems/contiguous-array/
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;

        int sum = 0;
        int ans = 0;
        hash[0] = -1; // 当和为sum = 0时，长度就是当前下标+1

        for (int i = 0; i<nums.size(); ++i)
        {
            if (nums[i])
                ++sum;
            else
                --sum;
            
            if (hash.count(sum))             
                ans = max(ans, i - hash[sum]);
            else 
                hash[sum] = i;
        }
        return ans;

    }

    // 1314. 矩阵区域和
    // https://leetcode.cn/problems/matrix-block-sum/
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> sum(m+1, vector<int>(n+1));
        vector<vector<int>> ans(m, vector<int>(n));
        int i = 0, j = 0;

        for (i=1; i<=m; ++i)
        {
            for (j=1; j<=n; ++j)
            {
                sum[i][j] = mat[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            }
        }
        
        for (i = 0; i<m; ++i)
        {
            for (j = 0; j<n; ++j)
            {
                int x1 = max(0, i-k) + 1;
                int y1 = max(0, j-k) + 1;
                int x2 = min(m-1, i+k) + 1;
                int y2 = min(n-1, j+k) + 1;
                ans[i][j] = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
            }
        }

        return ans;
    }
};